COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Debug your Thinking
C00017 ENDMK
C⊗;
Debug your Thinking

Think about the following problems and then run them on the machine.
Understand an unexpected result before attempting the next problem.


1. (CAR '(A B))

2. (CAR (QUOTE (A B)))

3. (CAR (QUOTE (QUOTE B)))

4. (CDR (QUOTE (CAR A B)))

5. (CONS (CAR '(A B)) (CDR '(A B)))

6. (EQUAL (CONS (CAR '(A B)) (CDR '(A B))) '(A B))

7. (EQ (CONS (CAR '(A B)) (CDR '(A B))) '(A B))

8. (CONS 'CDR  (QUOTE (A B)))

9. (CONS 'CDR '(QUOTE (A B)))

10. (CONS 'CDR '((QUOTE (A B))))

11. (CAR '(A B C))

12. (CDR '(A B C))

13. (CADR '(A B C))

14. (CDDR '(A B C))

15. (CADDR '(A B C))

16. (CDDDR '(A B C))

(CDR ''(A B C)))

(CAR ''(A B C))

(PLUS (CAR '(1 2)) 3)

(QUOTE (CAR A))

(EQ (CAR '(CONS A B)) (CAR (CONS 'A 'B)))

(QUOTE (CAR 1))

'(LAMBDA (X Y) (CAR (F X Y)))

(QUOTE 1)

(PLUS 1)

(PLUS)

(TIMES (PLUS 2 4) 5)

(LIST 1 2 3)

(CONS 1 (CONS 2 3))

(APPEND '(1  2) '(A B))

(CONS '(1 2) '(A B))

(LIST '(1 2) '(A B))

(EQUAL (LIST) (LIST NIL))

(ATOM (CAR (CONS 1 '(2))))

(CONS (ATOM (LIST 'CONS 2)) (ATOM (CAR '(CONS 2))))


(COND ((ATOM 'A) 1)
      (T (CONS (CADR 1) )))

(CONS (COND ((EQ 'A 'B) 3)
	    (T 'A))
      (CONS 'A '(B)))

(COND ((ATOM 'A))
      ((FOO BAR)))


--
((LAMBDA (X Y)(CONS X (CONS Y NIL))) 1 2)

((LAMBDA (X Y) (CONS Y (CADR X))) '(A (1 2)) 'Y)

((LAMBDA (X) (COND ((NULL X))
		   ((EQ (CAR X) 'A) 'B)
		   (T 2)))
 '(A B C))

((LAMBDA (X) (COND ((NULL X))
		   ((EQ (CAR X) 'A) 'B)
		   (T 2)))
 '(B B C))

As the above examples show, names are a useful abbreviation when repeated
application of a function is desired.

--

Evaluate: (DOG 'A '(A B B))

After installing:

(DE DOG (X Y)
  (COND ((NULL Y) 0)
	((EQ X (CAR Y)) (ADD1 (DOG X (CDR Y))))
	(T (DOG X (CDR Y)))))

Give an informal despription of DOG, including an analysis of its
expectations and limitations.

--
Assume we wanted to define a version of the IF expression that took
three arguments: (IF-3 <pred> <exp-a> <exp-b>), where we evaluate <exp-a> if <pred>
gives a non-NIL value, and evaluate <exp-b> otherwise.
Even though expressions like (IF-3 T 2 3) and (IF-3 NIL 3 4) give the
expected result, why does the following attempt fail:

(DE IF-3 (P A B)
  (COND (P A)
	(T B)))

--
1. Write  a  unary LISP  function,  LIST-OF-ATOMS, that  will  compute the  list  of
(unique) atoms in an arbitrary S-expression.
--
 Write a function PRED that will compute the precedcessor of a non-negative
integer. To make it interesting, the only arithmetic function you may use is ADD1.

--
****more *****

--------------------------------------------
tuesday
--
We wish to define a CASE expression of the form
(CASE <exp> -(<test> -<exps>-)- <exp>) evaluates <exp> and then
looks at the <test>s sequentially. If a <test> is an atom it is EQ-compared 
 against the value; if <test> is a list it is  MEMQ-compared against the value.
At the first non-NIL result, we return the value of the corresponding -<exps>-.
If all tests return NIL, we evaluate <exp1>.

Write a macro, defining CASE.

Note CASE has been in LISP since 1959 under the name SELECTQ, much pre-dating
Tony Hoare's re-discovery for Algol-like languages.

--
Write an iterative version of the COUNTATOMS  function.

--
Mapping functions: N. B. The order of arguments for the Interlisp mapping
functions is the reverse of that in the notes and the AIP book:

(AIP-map <function> <list>) = (Interlisp-map <list> <function>)

Evaluate:

(MAPCAR '(1 2 3 4 5) 'ADD1)

(MAPCAR '(1 2 3 4 5) '(LAMBDA (X) (PLUS X 1))

--
Property-list functions: 
N.B. (AIP-PUTPROP <symbol> <value> <property>) 
	   = (Interlisp-PUTPROP <symbol> <property> <value>)

Simple P-list examples. Evaluate the following in Interlisp:

(PUTPROP 'A 'B 'C)

(GETPROP 'A 'B)

(REMPROP 'A 'B)

(GETPROP 'A 'B)

--
rplaca/d

--
Write a function, LISTKEYS, that takes an association list and returns
a list of all the keys in it. Keys are the objects that ASSOC compare
against its first argument.

--
Recall the general store-macro, (:= <target> <value>) where <target> could
be (a) a symbol, (b) a slot in a CONS-cell,  or (c) a slot in a P-list.
Write a version of := without read-macros, and extend it to handle
A-lists: e.g (:= (KEY <name> <a-list>) <value>) drops a new value for the key, 
<name>, and if no such key exists, adds a new pair.
--

project
--------------------------------------------
wed/thurs

eval
 use
 write  eval for polys (with vars)
--------------------------------------------


	      II -----------A Simple data-base-------------

We want to investigate a data-base of  family trees. In particular, we want to  look
at the  "mother-hood"  relation (apple-pie-ness  comes  next week);  we  assume  all
individuals  in   our  base   are  female.    To  represent   the  relationship   "α
is-the-mother-of β", we will place  the name α on the  property-list of β under  the
property M-O (MOTHER OF).

(PUTPROP 'FELINA 'GILDA 'M-O) makes GILDA the mother of FELINA.

6.  Write a  function ADD whose  argument represents a  motherhood relationship  and
whose effect is to install that relationship in the data base.

eg (ADD '(GILDA M-O FELINA)) and (ADD '(GILDA M-O ISIS)) the ADD-function should  be
faithful to mother-ness (single mothers please ...hum).

7.Write a function called RETRIEVE whose  argument represents a MO-triple and  whose
value is T or NIL depending on whether the MO-relationship is in the base.

(RETRIEVE '(GILDA M-O FELINA)) should return NIL  before the above ADD is done,  and
should return T afterwards.

8. Write a binary predicate GRANDMOTHER, that will tell if the first argument is the
grandmother of the second.

9. Write  a binary  predicate,  SISTER, that  will tell  if  the two  arguments  are
sisters.

***For problem 10 you may find it useful to extend the ADD function.

10. Extend RETRIEVE to allow  retrieval of M-O values  by allowing variables in  the
arguments, where variables are represented as in problem 4.

For example: (RETRIEVE '(?X M-O FELINA)) should return ((X GILDA)).
	     (RETRIEVE '(GILDA M-O ?X))  should return ((X FELINA)(X ISIS)).


--------------------------------------------
project possibilities
 take from winstons's stuff since AIP  doesnt handle:
	vision
	rule-based experts
	symbolic math
	PROG EQUIVALENCE
	FREE-VARS-IN

	lmm: mini-dendral

 patten match
  unifier
 nl parsing
 simple expert system
 editor/debugger/interpreter
 simple ai language
 pratt parser

 infix to prefix, or inverse

harder problems
 n-queens
 searching and sorting
--------------------------------------------
program understanding problem p415, AI

is-a-get p420

define alternate

logo mystery

--------------------------------------------
2. Eight Queens Problem:  To place eight queens on a chess board such that
they do not threaten each other.  Queens in chess can move along  columns,
rows, and the two diagonals through their present position.

Define a data-structure  representation for  the board,  write a  function
that will tell whether  two queens threaten each  other, write a  function
that will tell if a new placement is safe, and write a function that  will
"backup"  the   tentative  placement,   removing   the  last   queen   and
repositioning her  in  another non-threatened  position  if there  are  no
non-threatened positions for her successor.  Use these components to write
a solution  to  the  eight queens  problem.  This  is classic  example  of
recursive backtracking.

(DE THREAT (I J M N)  ;i-j is the position of the first queen, a-b, the second.
    (OR (= I M)
	(= J N)
	(= (- I J) (- M N))
	(= (+ I J) (+ M N))))


(DE SAFE (I J BOARD)
	(COND (( NULL BOARD) T)
	      ((THREAT I J (ROW (FIRST BOARD))(COL (FIRST BOARD))) NIL)
	      (T (SAFE I J (REST BOARD)]


(DE Q ( ) (Q1 NIL 1 1 8 8))


(DE Q1 (BOARD I J POS SIZE)
  (COND	((= (LENGTH BOARD) SIZE) BOARD)
	((GREATERP J POS) BOARD)
	((GREATERP I SIZE) (Q1 (REST BOARD) 
			       (ADD1 (ROW (FIRST BOARD))) 
			       (COL (FIRST BOARD))
			       SIZE
			       SIZE))
	((SAFE I J BOARD) (Q1 (INCL (COOR I J) BOARD) 
			      1 
			      (ADD1 J) 
			      SIZE
			      SIZE))
	(T                       (Q1 (Q1 BOARD (ADD1 I) J J SIZE)
				     1
				     (ADD1 J)
				     SIZE
				     SIZE)))))

(DE FIRST (X) (CAR X))

(DE REST (X) (CDR X))

(DE COOR (I J)(CONS I J))
(DE INCL (X Y)(CONS X Y))

(DE ROW (X)(CAR X)))

(DE COL (X) (CDR X)))

(DE = (X Y)(EQUAL X Y))

(DE + (X Y) (PLUS X Y))

(DE - (X Y) (DIFFERENCE X Y)))
--------------------------------------------
phw solution

(DE QUEEN (SIZE)
  (PROG (N M BOARD)	
	(SETQ N 1)
  	LOOP-N
	(SETQ M 1)
	LOOP-M
	(COND ((CONFLICT N M BOARD) (GO UN-DO-M)))
	(SETQ BOARD (CONS (LIST N M) BOARD)
	(COND ((GREATERP (SETQ N (ADD1 N)) IZE)
	       (PRINT (REVERSE BOARD))))
	(GO LOOP-N)
	UN-DO-N
	(COND ((NULL BOARD) (RETURN 'FINISHED))
	      (T (SETQ M (CADAR BOARD)
		       N (CAAR BOARD)
		        BOARD (CDR BOARD))))
	UN-DO-M
	(COND ((GREATERP (SETQ M (ADD1 M)) SIZE)
	       (GO UN-DO-N))
	      (T (GO LOOP-M))))